import javafx.scene.layout.Priority;

import java.util.*;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Microsoft
 * Date: 2023-03-28
 * Time: 14:39
 */

class Student {
    private String id;

    public Student(){

    }
    public Student(String id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
public class Test {
    public static List<String> topKFrequent(String[] words, int k) {
        //1.遍历数组 统计每个单词出现的频率
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s:words) {
            if (hashMap.get(s) == null) {
                hashMap.put(s,1);
            }else {
                hashMap.put(s,hashMap.get(s) + 1);
            }
        }

        //2.建立小根堆  PriorityQueue默认是小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //3.遍历hashMap 把里面的数据放到小根堆
        for (Map.Entry<String,Integer> entry:hashMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                //小根堆放慢了k个，下一个entry和我们堆顶元素进行比较
                Map.Entry<String,Integer> top = minHeap.peek();
                //堆顶的频率小于当前entry的频率就出队，然后入队entry
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.add(entry);
                }else {
                    //频率相同的情况
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.add(entry);
                        }
                    }
                }
            }
        }

        //此时小根堆当中已经有了结果
//        System.out.println(minHeap);
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            ret.add(key);
        }
        Collections.reverse(ret);
//        System.out.println(ret);
        return ret;
    }

    public static void main(String[] args) {
        String[] words = {"a","b","a","c","d","a", "c","e","e","a","e"};
        topKFrequent(words,3);
    }

    public static void func(String str1, String str2) {
        Set<Character> set = new HashSet<>();

        //将str2转成大写+数组
        for (char ch: str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }

        //将str1转成大写+数组
        Set<Character> setBroken = new HashSet<>();
        for (char ch: str1.toUpperCase().toCharArray()) {
            if (!set.contains(ch) && !setBroken.contains(ch)) {
                setBroken.add(ch);
                System.out.println(ch);
            }
        }


    }
    public static void main10(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1, str2);
        }
    }
    public static int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }
    public static void main9(String[] args) {
        Map<Integer,Integer> map = new HashMap<>();
        int[] array = {1,1,2,3,4,5,6,7};
        for (int x:array) {
            if (!map.containsKey(x)) {
                map.put(x,1);
            }else {
                map.put(x, map.get(x)+1);
            }
        }
        System.out.println(map);
    }
    public static void main8(String[] args) {
        Set<Integer> set = new HashSet<>();
        int[] array = {1,1,2,3,4,5,6,7};
        for (int x:array) {
            if (!set.contains(x)) {
                set.add(x);
            }else {
                System.out.println(x);
                return;
            }
        }

    }

    public static void main7(String[] args) {
        Student student1 = new Student("1234");
        System.out.println(student1.hashCode());
        Student student2 = new Student("1234");
        System.out.println(student2.hashCode());
    }
    public static void main6(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(1,11);
        hashBuck.put(2,22);
        hashBuck.put(3,33);
        hashBuck.put(4,44);
        hashBuck.put(5,55);
        hashBuck.put(6,66);
        hashBuck.put(7,77);
        hashBuck.put(8,88);

        System.out.println(hashBuck.get(5));
    }
    public static int firstUniqChar(String s) {
        int[] arr = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i)-'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (arr[s.charAt(i)-'a'] == 1){
                return i;
            }
        }
        return -1;
    }

    public static void main5(String[] args) {
        Set<String> set1 = new TreeSet<>();
        set1.add("hello");
        set1.add("this");
        set1.add("hello");
        System.out.println(set1);
        System.out.println(firstUniqChar("abca"));
    }
    public static void main3(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int i = (int)(Math.pow(5,5));
        int k = 1;
        int a = 0;
        while (k*i-4 <= n) {
            a++;
            k++;
            System.out.println(k*i-4 + " ");
        }

        if (a == 0) {
            System.out.println("impossible");
        }

    }
    public static void main1(String[] args) {
        Map<Student,Integer> treeMap = new TreeMap<>();
        //key一定是可以比较的
//        treeMap.put(new Student(),1);
//        treeMap.put(new Student(),2);
        System.out.println(treeMap);
    }


    public static void main2(String[] args) {
        Map<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("abc",4);
        treeMap.put("hello",3);
        treeMap.put("the",8);
        treeMap.put(null,8);


//        Set<String> ketset = treeMap.keySet();//将获取到的所有的key
//        System.out.println(ketset);

//        System.out.println("==========");
        Set<Map.Entry<String,Integer>> set = treeMap.entrySet();
        for (Map.Entry<String,Integer> entry:set) {
            System.out.println("key:"+entry.getKey() + "value:" + entry.getValue());
        }

    }
}


//public static void main1(String[] args) {
//        Scanner in = new Scanner(System.in);
//        while (in.hasNextInt()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
//            int a = in.nextInt();
//            int b = in.nextInt();
//            for (int i = Math.min(a,b); i <= a*b; i ++) {
//                if (i % a == 0 && i % b == 0) {
//                    System.out.println(i);
//                }
//            }
//        }
//    }
//    public static void main(String[] args) {
//        BinarySearchTree binarySearchTree = new BinarySearchTree();
//        binarySearchTree.insert(2);
//        binarySearchTree.insert(1);
//        binarySearchTree.insert(5);
//        binarySearchTree.insert(18);
//        binarySearchTree.insert(9);
//        binarySearchTree.inorder(binarySearchTree.root);
//
//
//        System.out.println();
//        binarySearchTree.remove(9);
//        binarySearchTree.inorder(binarySearchTree.root);
//
//    }


